#include<stdio.h>
#include<malloc.h>

#define block 655360
typedef struct pool{
	int* data;
	struct pool* next;
} p;

void insert(int n,p* head,int* s,int* count){
	int index,t;
	p* cur;
	p* tmp;
	t = *s;
	if(*count < block){
		index = *count;
	}else{
		index = (*count) % block;
	}
	cur = head;
	while(t > 0){
		cur = cur->next;
		--t;
	}
	if(index || *count == 0){
		*(cur->data + index ) = n;
	}else{
		tmp = (p*)malloc(sizeof(p));
		tmp->data = (int*)malloc(sizeof(int) * block);
		*(tmp->data) = n;
		cur->next = tmp;
		++(*s);
	}
	++(*count);
}

int test(int n,int* data,int b){
	int i;
	for(i=0;i<=b;++i){
		if(n % (*(data + i)) == 0){
			return 1;
		}
	}
	return 0;
}

int is_prime(int n,p* head,int s,int count){
	p* next;
	if(n < 2){
		return 0;
	}
	if(count == 0){
		return 1;
	}
	next = head;
	while(s > 0 || (s == 0 && count % block == 0 && count > 0)){
		if(test(n,next->data,block - 1)){
			return 0;
		}
		next = next->next;
		--s;
	}
	if(s == 0){}
	if(count % block != 0){
		if(test(n,next->data,count % block - 1)){
			return 0;
		}
	}
	return 1;
}

int main(int argc,char* argv){
	int s = 0,count = 0,i,n=655360;
	p* head = (p*)malloc(sizeof(p));
	head->data = (int*)malloc(sizeof(int)*block);
	head->next = NULL;
	if(n<=2){
		//printf("%d\n",n);
		return 0;
	}
	//printf("2 ");
	for(i=3;i<n;i+=2){
		if(is_prime(i,head,s,count)){
			insert(i,head,&s,&count);
			//printf("%d ",i);
		}
	}
	return 0;
}
